//原文链接
//@https://blog.csdn.net/ITSOK_123/article/details/124647498
//递归（O(N),O(N)）
bool compare(TreeNode* left, TreeNode* right){
        if(left ==nullptr && right !=nullptr) return false;
        else if(right == nullptr && left!= nullptr) return false;
        else if(right == nullptr && right == nullptr) return true;
        else if(right->val != left->val)    return false;
        else {
            return compare(left->left,right->right)&&
            compare(left->right,right->left);
        }
    }
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;
        return compare(root->left,root->right);
    }


//迭代（O(N),O(N)）
bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;
        // 队列保存迭代过程
        queue<TreeNode*> que;
        // 确保每次入队相邻两个元素是位置对称的
        que.push(root->left);
        que.push(root->right);
        while(!que.empty()){
            TreeNode *lts = que.front();
            que.pop();
            TreeNode *rts = que.front();
            que.pop();
            // 左右节点均为空则继续
            if(!lts && !rts) continue;
            // 左右节点有一个不为空则不对称
            if(!lts ||!rts)    return false;
            // 左右节点均不为空且值不相等则不对称
            if(lts->val != rts->val) return false;
            // 按照镜像进行入队
            que.push(lts->left);
            que.push(rts->right);
            que.push(lts->right);
            que.push(rts->left);
        }
        return true;
    }
